|
In computer science, a parallel random-access machine (PRAM) is a shared-memory abstract machine. As its name indicates, the PRAM was intended as the parallel-computing analogy to the random-access machine (RAM). In the same way that the RAM is used by sequential-algorithm designers to model algorithmic performance (such as time complexity), the PRAM is used by parallel-algorithm designers to model parallel algorithmic performance (such as time complexity, where the number of processors assumed is typically also stated). Similar to the way in which the RAM model neglects practical issues, such as access time to cache memory versus main memory, the PRAM model neglects such issues as synchronization and communication, but provides any (problem-size-dependent) number of processors. Algorithm cost, for instance, is estimated using two parameters O(time) and O(time × processor_number). ==Read/write conflicts== Read/write conflicts in accessing the same shared memory location simultaneously are resolved by one of the following strategies: #Exclusive read exclusive write (EREW)—every memory cell can be read or written to by only one processor at a time #Concurrent read exclusive write (CREW)—multiple processors can read a memory cell but only one can write at a time #Exclusive read concurrent write (ERCW)—never considered #Concurrent read concurrent write (CRCW)—multiple processors can read and write. A CRCW PRAM is sometimes called a concurrent random-access machine.〔Neil Immerman, ''Expressibility and parallel complexity''. Siam Journal on Computing, vol. 18, no. 3, pp. 625-638, 1989.〕 Here, E and C stand for 'exclusive' and 'concurrent' respectively. The read causes no discrepancies while the concurrent write is further defined as: ::''Common''—all processors write the same value; otherwise is illegal ::''Arbitrary''—only one arbitrary attempt is successful, others retire ::''Priority''—processor rank indicates who gets to write ::Another kind of ''array reduction'' operation like SUM, Logical AND or MAX. Several simplifying assumptions are made while considering the development of algorithms for PRAM. They are: # There is no limit on the number of processors in the machine. # Any memory location is uniformly accessible from any processor. # There is no limit on the amount of shared memory in the system. # Resource contention is absent. # The programs written on these machines are, in general, of type SIMD. These kinds of algorithms are useful for understanding the exploitation of concurrency, dividing the original problem into similar sub-problems and solving them in parallel. The introduction of the formal 'P-RAM' model in Wyllie's 1979 thesis〔Wyllie, James C. The Complexity of Parallel Computations, PhD Thesis, Dept. of Computer Science, Cornell University〕 had the aim of quantifying analysis of parallel algorithms in a way analogous to the Turing Machine. The analysis focused on a MIMD model of programming using a CREW model but showed that many variants, including implementing a CRCW model and implementing on an SIMD machine, were possible with only constant overhead. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Parallel random-access machine」の詳細全文を読む スポンサード リンク
|